package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//将节点全部保存队列:4ms 34%,2.7MB 13%
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	res, queue := [][]int{}, [][]*TreeNode{{root}}
	for i := 0; i < len(queue); i++ {
		res = append(res, []int{})
		for j := 0; j < len(queue[i]); j++ {
			if queue[i][j].Left != nil || queue[i][j].Right != nil {
				queue = append(queue, []*TreeNode{})
				break
			}
		}
		for j := 0; j < len(queue[i]); j++ {
			res[i] = append(res[i], queue[i][j].Val)
			if queue[i][j].Left != nil {
				queue[i+1] = append(queue[i+1], queue[i][j].Left)
			}
			if queue[i][j].Right != nil {
				queue[i+1] = append(queue[i+1], queue[i][j].Left)
			}
		}
	}
	return res
}

//节点逐层替换:0ms 100%,2.6MB 95%
func levelOrder1(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	res, queue := [][]int{}, []*TreeNode{root}
	for i := 0; len(queue) > 0; i++ {
		res = append(res, []int{})
		tmp := []*TreeNode{}
		for _, v := range queue {
			res[i] = append(res[i], v.Val)
			if v.Left != nil {
				tmp = append(tmp, v.Left)
			}
			if v.Right != nil {
				tmp = append(tmp, v.Right)
			}
		}
		queue = tmp
	}
	return res
}

func main() {
	fmt.Println(levelOrder(&TreeNode{}))
	fmt.Println(levelOrder1(&TreeNode{}))
}
